/*
 * @lc app=leetcode.cn id=493 lang=java
 *
 * [493] 翻转对
 */

// @lc code=start
class Solution {
    public int reversePairs(int[] nums) {
        int n = nums.length;
        if(n < 2)
            return 0;
        
        int[] helper = new int[n];
        return reverse(nums, helper, 0, n-1);
    }

    // 返回 nums[l..r] 中翻转对的个数
    private int reverse(int[] nums, int[] helper, int l, int r) {
        if(l == r) {
            return 0;
        }
        int mid = l + (r - l) / 2;

        // 左边翻转对的个数
        int leftResult = reverse(nums, helper, l, mid);
        // 右边翻转对的个数
        int rightResult = reverse(nums, helper, mid+1, r);
        //跨区间的翻转对的个数
        int crossResult = merge(nums, helper, l, mid, r);
        
        return leftResult + rightResult + crossResult;
    }

    public int merge(int[] nums, int[] helper, int l, int mid, int r) {
        int ans = 0;
        int count = 0;
        for(int i = l, j = mid + 1; i <= mid; i++) {
            while(j <= r && (long)nums[i] > 2 * (long)nums[j]) {
                count++;
                j++;
            }
            ans += count;
        }

        int i = l, j = mid + 1, p = l;
        while(i <= mid && j <= r) {
            if(nums[i] <= nums[j]) {
                helper[p++] = nums[i++];
            } else {
                helper[p++] = nums[j++];
            }
        }

        while(i <= mid) {
            helper[p++] = nums[i++];
        }

        while(j <= r) {
            helper[p++] = nums[j++];
        }

        for(int k = l; k <= r; k++) {
            nums[k] = helper[k];
        }

        return ans;
    }
}
// @lc code=end

